package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月12日
*时间：下午5:21:19
*/
public class Q116 {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    public boolean canJump(int[] A) {
        if (A == null || A.length <= 1) {
            return true;
        }
        int length = A.length;
        boolean[] canJump = new boolean[length];
        canJump[length - 1] = true;
        for (int i = length - 2; i >= 0; i--) {
            if (i + A[i] >= length) {
                canJump[i] = true;
            } else {
                for (int j = 0; j <= A[i]; j++) {
                    canJump[i] |= canJump[i + j];
                }
            }
        }
        return canJump[0];
    }

    @Test
    public void testA() {
        int[] A = { 3, 2, 1, 0, 4 };
        System.out.println(canJump(A));
    }
}
